package com.example.algorithm.dynamicprogramming;

/**
 * 给你一个整数数组 nums 和一个整数 target 。
 *  向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 *  例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 *  返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 *
 *  示例 1：
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 *
 *  示例 2：
 * 输入：nums = [1], target = 1
 * 输出：1
 *
 *  提示：
 *  1 <= nums.length <= 20
 *  0 <= nums[i] <= 1000
 *  0 <= sum(nums[i]) <= 1000
 *  -1000 <= target <= 1000
 */
public class Leetcode494_FindTargetSumWays {
    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1};
        int target = 3;
        System.out.println(new Solution().findTargetSumWays(nums, target));

    }

    static class Solution {
        /**
         * 解法二:动态规划
         * 记数组的元素和为sum，添加 - 号的元素之和为 neg，则其余添加 + 的元素之和为sum−neg，得到的表达式的结果为
         *  (sum−neg)−neg = sum−2*neg=target  =>   neg = (sum -target) / 2
         *
         * 问题转化成在数组nums 中选取若干元素，使得这些元素之和等于 neg
         *
         * 1.子问题:
         *   前 i个元素中选取若干元素,使得之和等于j
         *
         * 2.状态定义:
         *   dp[i][j] 表示在数组 nums 的前 i个数中选取元素，使得这些元素之和等于 j 的方案数
         *   目标值:dp[n][neg] 其中neg = (sum -target) / 2
         *
         * 3.状态转移方程:
         *   当 1 <= i <=n 时，对于数组nums 中的第 i 个元素 num（i 的计数从 1 开始），遍历 0 <= j <= neg，计算 dp[i][j] 的值
         *     如果 j < num，则不能选 num，此时有 dp[i][j]=dp[i−1][j]
         *     如果 j >= num，则
         *         如果不选 num，方案数是 dp[i−1][j]，
         *         如果选 num，方案数是 dp[i−1][j−num]，此时有 dp[i][j] = dp[i−1][j] + dp[i−1][j−num]。
         *
         * 4.边界条件:
         *   dp[0][j]= 0 (j=0)
         *   dp[0][j]= 1 (j>0)
         * @param nums
         * @param target
         * @return
         */
        public int findTargetSumWays2(int[] nums, int target) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
            int diff = sum - target;
            if (diff < 0 || diff % 2 != 0) // 根据推导可知不满足这两个条件的必定不存在方案
                return 0;
            int n = nums.length, neg = diff / 2;
            int[][] dp = new int[n + 1][neg + 1]; // 在数组 nums 的前 i个数中选取元素，使得这些元素之和等于 j 的方案数
            dp[0][0] = 1;
            for (int i = 1; i <= n; i++) {
                int num = nums[i - 1];
                for (int j = 0; j <= neg; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= num) {
                        dp[i][j] += dp[i - 1][j - num];
                    }
                }
            }
            return dp[n][neg];
        }

        /**
         * 解法一:回溯法
         * 每个数字可以有+/-操作,一共就有2^n种表达式,枚举所有的表达式，判断最终结果是否是target
         * @param nums
         * @param target
         * @return
         */
        int count = 0;
        public int findTargetSumWays1(int[] nums, int target) {
            backTrace(nums, target, 0, 0);
            return count;
        }

        private void backTrace(int[] nums, int target, int index, int sum) {
            if (index == nums.length) {
                if (sum == target) count++;
            } else {
                backTrace(nums, target, index + 1, sum + nums[index]);
                backTrace(nums, target, index + 1, sum - nums[index]);
            }
        }


        public int findTargetSumWays(int[] nums, int target) {
            return findTargetSumWays1(nums, target);

        }
    }
}
